/**
 * @param {string} word1
 * @param {string} word2
 * @return {{distance: number, operations: string[]}}
 */
function minDistanceWithOperations(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  const operations = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(''));

  // 初始化第一行和第一列
  for (let i = 0; i <= n; i++) {
    dp[0][i] = i;
    operations[0][i] = `Insert '${word2[i - 1] || ''}' at position ${i - 1}`;
  }
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;
    operations[i][0] = `Delete '${word1[i - 1] || ''}' at position ${i - 1}`;
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
        operations[i][j] = 'No operation';
      } else {
        const insert = dp[i][j - 1] + 1;
        const del = dp[i - 1][j] + 1;
        const replace = dp[i - 1][j - 1] + 1;

        if (insert <= del && insert <= replace) {
          dp[i][j] = insert;
          operations[i][j] = `Insert '${word2[j - 1]}' at position ${j - 1}`;
        } else if (del <= insert && del <= replace) {
          dp[i][j] = del;
          operations[i][j] = `Delete '${word1[i - 1]}' at position ${i - 1}`;
        } else {
          dp[i][j] = replace;
          operations[i][j] = `Replace '${word1[i - 1]}' with '${word2[j - 1]}' at position ${i - 1}`;
        }
      }
    }
  }

  // 回溯操作过程
  const resultOperations = [];
  let i = m, j = n;
  while (i > 0 || j > 0) {
    if (operations[i][j] !== 'No operation') {
      resultOperations.push(operations[i][j]);
    }
    if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + (word1[i - 1] === word2[j - 1] ? 0 : 1)) {
      i--;
      j--;
    } else if (j > 0 && dp[i][j] === dp[i][j - 1] + 1) {
      j--;
    } else {
      i--;
    }
  }

  return {
    distance: dp[m][n],
    operations: resultOperations.reverse()
  };
};

// 示例
const word1 = "horse", word2 = "ros";
const result = minDistanceWithOperations(word1, word2);
console.log(result);